Data compression is a well known art for reducing the amount of data (e.g., the number of bits) comprising a file or object. The use of data compression is popular for the purposes of both transmission and storage. In typical implementations, data compression is achieved via the use of algorithms which reduce or eliminate unnecessary repetition of data by encoding the information used to represent the data to a smaller, more efficient amount of data.
Algorithms, such as Variable length Coding (VLC) or Context-Adaptive Variable Length Coding (CAVLC) may be used to reduce the number of bits that are needed to represent the image. In typical data compression schemes, a prefix code is used for integers that maps positive integers to binary code words. In general, most prefix codes for integers assign longer code words to larger integers. Such a code can be used to efficiently communicate a message drawn from a set of possible messages, by simply ordering the set of messages according to decreasing probability and then sending the index of the intended message.
Exp-Golomb Coding is one example of Context Adaptive Variable Length Coding. Exp-Golomb codes are variable length codes and are widely used in the Advanced Video Coding (AVC) (e.g., H.264). However, as with other variable-length codes (e.g., Huffman code), decoding Exp-Golomb codes may be somewhat difficult, because the input data length is varied and unpredictable.
In a typical Exp-Golomb encoding algorithm, all of the individual code words of a given Exp-Golomb code set are uni Expue. Also, the n most significant bits (MSBs) of a given code word are always different from any other code word having length of n. Further, a Exp-Golomb code word consists of a number of “leading bits” followed by another number of value bits used to help specify the value of the particular code word. The number of value bits (typically) being one less than that of the leading bits. The leading bits of a code word contain a number of leading 0 bits followed by one 1 bit. The number of leading 0 bits is the same as that of the number of value bits for the code word. For shorter code words (e.g., single digit code words), if the leading bit length is 1, there are no leading 0 and value bit for that code word.
Conventional techniques for encoding Exp-Golomb codes often include the use of table mapping to look-up a code number corresponding to a given code word. In such a technique, the number of entries in the decoding look-up table may equal 2^(longest possible code length). For example, if the maximum code length is 8, then the table may have 28 (256) entries, with longer code lengths typically requiring an exponentially larger memory size for the table. Since code lengths are variable and lengths of up to 16 and even 32 bits are typical, the size of the memory required for the look-up table can be substantial, requiring large silicon areas to implement in hardware. In addition, the time required to serially traverse large look-up tables may also be significant, and result in unnecessary conversion delays.
Furthermore these techniques are generally applicable only to unsigned input and to generate unsigned Exp-Golomb code as output. Accordingly, encoding signed (e.g., negative) input typically requires an extra conversion from the signed input into a positive input prior to conversion to Exp-Golomb code. Naturally, this intermediate conversion may require additional components or consume additional processing time to perform.